package com.platform.modules.alg.alglib.poj1988;

public class Poj1988 {
    public String output = "";

    private final int N = 30010;
    int n;
    int fa[] = new int[N];
    int d[] = new int[N];
    int cnt[] = new int[N];

    void Init() {
        for (int i = 1; i < N; i++) {
            fa[i] = i;
            d[i] = 0;
            cnt[i] = 1;
        }
    }

    int Find(int x) {
        int fx = fa[x];
        if (x != fa[x]) {
            fa[x] = Find(fa[x]);
            d[x] += d[fx];
        }
        return fa[x];
    }

    void Union(int x, int y) {
        int a, b;
        a = Find(x);
        b = Find(y);
        fa[a] = b;
        d[a] = cnt[b];
        cnt[b] += cnt[a];
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        Init();
        for (int count = 0; count < n; count++) {
            String[] words = line[count + 1].split(" ");
            if (words[0].charAt(0) == 'C') {
                int i = Integer.parseInt(words[1]);
                Find(i);
                output += "" + d[i] + "\n";
            } else {
                int i = Integer.parseInt(words[1]);
                int j = Integer.parseInt(words[2]);
                Union(i, j);
            }
        }
        return output;
    }
}
